package lcr;

import java.util.Arrays;

public class Test0059 {
    public static void main(String[] args) {
        int[] nums = {4,5,8,2};
        KthLargest kthLargest = new KthLargest(3, nums);
        System.out.println(kthLargest.add(3));   // return 4
        System.out.println(kthLargest.add(5));   // return 5
        System.out.println(kthLargest.add(10));  // return 5
        System.out.println(kthLargest.add(9));   //
    }
}

class KthLargest {
    private MinHeap minHeap;

    public KthLargest(int k, int[] nums) {
        minHeap = new MinHeap(k);
        for (int num : nums) {
            add(num);
        }
    }

    public int add(int val) {
        if (!minHeap.isFull()) {
            minHeap.offer(val);
        } else if (minHeap.peek() < val) {
            minHeap.replace(val);
        }
        return minHeap.peek();
    }

    public class MinHeap {
        int[] array;
        int size;

        public MinHeap() {
        }

        public MinHeap(int capacity) {
            this.array = new int[capacity];
        }

        public MinHeap(int[] array) {
            this.array = array;
            this.size = array.length;
            heapify();
        }

        private void heapify() {
            for (int i = size - 1; i >= 0; i--) {
                down(i);
            }
        }

        public void replace(int replaced) {
            array[0] = replaced;
            down(0);
        }

        public boolean offer(int offered) {
            if (isFull()) {
                return false;
            }
            up(offered);
            size++;
            return true;
        }

        private void up(int offered) {
            int child = size;
            while (child > 0) {
                int parent = (child - 1) / 2;
                if (offered < array[parent]) {
                    array[child] = array[parent];
                } else {
                    break;
                }
                child = parent;
            }
            array[child] = offered;
        }

        public int poll(int index) {
            int deleted = array[index];
            swap(index, 0);
            size--;
            down(index);
            return deleted;
        }

        public int peek() {
            return array[0];
        }

        public int poll() {
            int top = array[0];
            swap(0, size - 1);
            size--;
            down(0);
            return top;
        }

        private void down(int parent) {
            int left = parent * 2 + 1;
            int right = left + 1;
            int min = parent;
            if (left < size && array[left] < array[min]) {
                min = left;
            }
            if (right < size && array[right] < array[min]) {
                min = right;
            }
            if (min != parent) {
                swap(min, parent);
                down(min);
            }
        }

        private void swap(int i, int j) {
            int t = array[i];
            array[i] = array[j];
            array[j] = t;
        }

        private boolean isEmpty() {
            return size == 0;
        }

        private boolean isFull() {
            return size == array.length;
        }
    }
}